package com.hyb.algorithm.data.struct.tree;

/**
 * @Author: huyanbing
 * @Date: 2021/8/13 2:03 下午
 */
public class BinarySearch {

    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 2, 2, 3};
        int target = 2;


        BinarySearch binarySearch = new BinarySearch();

        //应该返回 1  但是结果是 2 中间的那个
        System.out.println(binarySearch.binarySearch(nums, 2));

        // 返回小于 target的 个数
        System.out.println(binarySearch.binarySearchBound(nums, 2));
    }


    /**
     * 2,2  寻找边界的二分查找法
     * 二分查找法
     *
     * @param nums
     * @param val
     * @return
     */
    private int binarySearchBound(int[] nums, int val) {

        if (nums.length <= 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length;


        //终止条件是  [left,left)
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == val) {
                right = mid;
            } else if (nums[mid] > val) {
                right = mid;
            } else if (nums[mid] < val) {
                left = mid + 1;
            }
        }


        /**
         * // target ⽐所有数都⼤
         * if (left == nums.length) return -1;
         * // 类似之前算法的处理⽅式
         * return nums[left] == target ? left : -1;
         */

        return left;

    }

    /**
     * 2,2
     * 二分查找法
     * 这样查找的  比如
     *
     * @param nums
     * @param val
     * @return
     */
    private int binarySearch(int[] nums, int val) {

        if (nums.length <= 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;


        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == val) {
                return mid;
            } else if (nums[mid] > val) {
                right = mid - 1;
            } else if (nums[mid] < val) {
                left = mid + 1;
            }
        }

        return -1;

    }


//    int binarySearch(int[] nums, int target) {
//        int left = 0;
//        int right = nums.length - 1; // 注意
//        while (left <= right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == target) {
//                return mid;
//            } else if (nums[mid] < target) {
//                left = mid + 1; // 注意
//            } else if (nums[mid] > target) {
//                right = mid - 1; // 注意
//            }
//        }
//        return -1;
//    }
}
